Java 集合类学习 Deque 双端队列
什么是双端队列？
双端队列（Double-ended queue）是与队列类似的有序集合。它有一前、一后两端，元素在其中保持自己的位置。与队列不同的是，双端队列对在哪一端添加和移除元素没有任何限制。新元素既可以被添加到前端，也可以被添加到后端。同理，已有的元素也能从任意一端进行移除。某种意义上，双端队列是栈和队列的结合。
Deque 接口
注意：Deque 既可以用作后进先出的栈，也可以用作先进先出的队列。
Deque 接口定义如下:
public interface Deque<E> extends Queue<E> {
// *** Deque methods ***
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);
// *** Queue methods ***
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
// *** Stack methods ***
void push(E e);
E pop();
// *** Collection methods ***
boolean remove(Object o);
boolean contains(Object o);
public int size();
Iterator<E> iterator();
Iterator<E> descendingIterator();
}
双端队列方法
插入
- addFirst 和 offerFirst 在 Deque 实例头部插入元素。
- addLast 和 offerLast 在 Deque 实例尾部插入元素。
当 Deque 实现类为有限容量时，优先使用 offerFirst 和 offerLast，因为 addFirst 在队列满的时候可能会插入失败而抛出异常。
删除
- removeFirst 和 pollFirst 从 Deque 实例头部移除元素。
- removeLast 和 pollLast 从 Deque 实例尾部移除元素。
当 Deque 为空时，pollFirst 和 pollLast 将会返回 null，而 removeFirst 和 removeLast 将会抛出异常。
检索
getFirst 和 peekFirst 获取 Deque 实例的第一个元素，但是不会将元素从 Deque 实例中删除。类似地，getLast 和 peekLast 获取最后一个元素。当 Deque 为空时，getFirst 和 getLast 将会抛出异常，而 peekFirst 和 peekLast 将会返回 null。
除了基本的插入、删除和检索方法外，还有两个预定义的方法：removeFirstOccurence 和 removeLastOccurence。这两个方法见名知意。返回 true 的时候表示元素存在于队列，并且已经被删除。返回 false 时表示元素不存在于队列中，并且队列没有改变。
Deque 接口实现类
Java 集合框架对 Deque 接口有几类实现：数组（Resizable Array）、链表（Linked List）。
ArrayDeque：数组实现
LinkedList：链表实现
LinkedList 内部结构
LinkedList 底层的数据结构是基于双向循环链表的，且头结点中不存放数据,如下：
LinkedList 包含两个重要的成员：header 和 size。
- header 是双向链表的表头，它是双向链表节点所对应的类 Entry 的实例；
- size 是双向链表中节点的个数。
既然是双向链表，那么必定存在一种数据结构——我们可以称之为节点，节点实例保存业务数据，前一个节点的位置信息和后一个节点位置信息，如下图所示：
Entry 中包含成员变量：previous, next, element
- previous 是该节点的上一个节点
- next 是该节点的下一个节点
- element 是该节点所包含的值。
访问性 LinkedList 实际上是通过 双向链表 去实现的。既然是双向链表，那么它的顺序访问会非常高效，而随机访问效率比较低。
LinkedList 是双向链表，但是它也实现了 List 接口，也就是说，它实现了 get(int index)、remove(int index) 等根据索引值来获取、删除节点的函数。
它增删一个元素会比较方便
public boolean add(E e) {
linkLast(e);
return true;
}
// 因为是双向链表，所以直接更改最后一个元素的指向就行了
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
前面说了 LinkedList 继承自 AbstractSequentialList，AbstractSequentialList 内部优化了对于链表这种 List 随机访问的能力，内部维护一个计数索引值
例如，当程序调用 get(int index) 方法时，首先会比较 Location 和双向链表长度的 1/2；如果前者大，则从链表头开始向后查找，直到 Location 位置；否则，从链表末尾开始向前查找，直到 Location 位置。（注意，这个不是二分法，它还是遍历实现的）
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
所以每次随机访问都是需要遍历一遍数组，而当访问的元素位于 List 中间，那就是花费最长的时候
双端队列的使用
使用例：
import java.util.Deque;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
Deque<String> deque = new LinkedList<>();
deque.offerLast("A"); // A
deque.offerLast("B"); // A <- B
deque.offerFirst("C"); // C <- A <- B
System.out.println(deque.pollFirst()); // C, 剩下A <- B
System.out.println(deque.pollLast()); // B, 剩下A
System.out.println(deque.pollFirst()); // A
System.out.println(deque.pollFirst()); // null
}
}
如果直接写 deque.offer()，我们就需要思考，offer() 实际上是 offerLast()，如果我们明确地写上 offerLast()，那么不需要思考就能一眼看出这是添加到队尾。因此，使用 Deque，推荐总是明确调用 offerLast()/offerFirst() 或者 pollFirst()/pollLast() 方法。
Deque 是一个接口，它的实现类有 ArrayDeque 和 LinkedList。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
我们发现 LinkedList 真是一个全能选手，它即是 List，又是 Queue，还是 Deque。但是我们在使用的时候，总是用特定的接口来引用它，这是因为持有接口说明代码的抽象层次更高，而且接口本身定义的方法代表了特定的用途。
// 不推荐的写法:
LinkedList<String> d1 = new LinkedList<>();
d1.offerLast("z");
// 推荐的写法：
Deque<String> d2 = new LinkedList<>();
d2.offerLast("z");
Deque 用作 Stack
Deque 数据结构也可以被用作 Stack栈（LIFO），Java 官方也建议开发者使用 Deque 取代旧版 Stack 类。当 Deque 被当作栈使用时，元素都从队头（Head）出入栈。Deque 也定义了栈的基本操作方法。
| Stack Method | Equivalent Deque Method |
|---|---|
| push(e) | addFirst(e) |
| pop() | removeFirst() |
| peek() | peekFirst() |
表：Deque 与 Stack 方法比较表
import java.util.Deque;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
/* Create a stack of strings based on deque */
Deque<String> aStack = new LinkedList<String>();
/* Push elements to stack */
aStack.push("Java");
aStack.push("Python");
aStack.push("JavaScript");
aStack.push("C/C++");
aStack.push("Golang");
/* Print stack details */
showDeque("Stack", aStack);
/* Pop elements from stack */
while (!aStack.isEmpty()) {
String e = aStack.pop();
System.out.println(e);
}
/* Print stack details */
showDeque("Stack", aStack);
}
public static <T> void showDeque(String name, Deque<T> deque) {
System.out.printf(
"%s(%d): %s" +
System.getProperty("line.separator"),
name, deque.size(), deque.toString()
);
}
}